伸展树（splay tree）

发表于 | | 阅读次数:

什么是伸展树？

首先，伸展树(splay tree)是一颗二叉搜索树，它的定义是建立在二叉搜索树之上，并且它是基于类似程序局部性原理的假设：一个节点在一次被访问后，这个节点很可能不久再次被访问。那么伸展树的做法就是在每次一个节点被访问后，我们就把它推到树根的位置。正像程序局部性原理的实际效率被广泛证明一样，伸展树在实际的搜索效率上也是非常高效的。尽管存在最坏情况下单次操作会花费O(N)的时间，但是这种情况并不是经常发生，而实际证明伸展树能够保证M次连续操作最多花费O(MlogN)的时间。

相比于平衡二叉树，伸展树有差不多的平均性能，其他的优势在于：不需要存储平衡信息。另外如果采用自顶向下的调整方式，还能简略额外的栈开销。

如何在查找的一个节点时调整树？

大多数博客上来就说单旋转，一字型，之字形的情况以及如何调整，我觉得这没有说清楚为什么要用这样的调整策略，并不利于我们深入理解这种策略背后的考量。要理解这个问题，我们需要自底向上的调整方式说起。

如果让我们自己设计伸展树查找后的伸展策略，目标是将查找到的节点调整到根节点的位置，我们的第一想法很简单，直接单旋转就好了，也就两种情况，一直循环到被查到的节点到根节点便是，但是这种做法会把不是被查找节点推到和原来被查询节点差不多的位置。一个简单的例子就是查询只有左子树的有序二叉查找树1,2……，9，

  1. 如果我们查询1，则1需要9次比较，查询结束后，将1逐步单旋转到树根位置，此时的树形是1为树根只有右孩子9,9节点只有左子树。
  2. 如果继续查询2，则也需要9次比较，查询结束后使用单旋转将2转到树根位置
  3. 如果继续查询节点3，则需要8次比较

也就是说以此类推，如果节点数是N的话，我们需要$N+\sum_{i=2}^{N} i=\Omega(N^2)$次查询时间。这种简单的旋转虽然把查询的节点推到的根节点，单也把其他节点推到了和它相似的深度，我们想以何种方法即可以即可以把根节点推到树根的位置，又可以进可能减少其他节点被推的深度，于是我们有了伸展的旋转方式。

伸展（splaying）

伸展是一种特殊的旋转方式，它采用了类似于平衡二叉树的策略，如果查询节点可以通过两步旋转更快的到达根节点，则采用两步旋转法。所谓的单旋转，一字型，之字形，是根据父节点是否是根节点来划分的，并且是自底向上的思路。
如果查询节点的父节点是根节点，那么直接旋转该节点到根节点的位置。
如果查询节点的父节点不是根节点，那么该节点一定有祖父节点，那么就分为两种情况1）之字形，查询节点是祖父节点的左儿子的右儿子或者右儿子的左儿子，这种情况按照平衡二叉树的左右或右左不平衡情况的旋转方式即可将查询节点旋转到祖父节点位置，2）一字型，如果查询节点是祖父节点的右儿子的右儿子，那么这种情况需要先将父节点换到祖父节点的位置，然后在将查询节点旋转到父节点位置。具体如下图所示。



图1：之字形旋转结果



图2：一字型旋转结果

图中Z节点为查询节点，如果仅从旋转的动作来看，之字形旋转的过程和简单旋转的的结果是相同的，而一字型则不同，从其过程来看，它是先旋转其父节点到祖父节点，然后再旋转查询节点到父节点，而简单旋转总是先旋转查询节点。

那么这种旋转的改变会带来哪些不一样的结果？
我们用原来的例子来解释，如1-7的树对1进行查询后按伸展方式进行旋转，其结果如图3所示，在将1推到根的情况下，这个树的高度在降低，其他的节点并没有因为1成为树根而被推到更深的位置，而我们看图4，仅使用单次旋转的简单旋转的结果，其深度并没有发生改变，而所有节点的深度都因为1成为根加了1.


图3：伸展方式旋转结果



图3：简单旋转方式的结果

自顶向下的伸展树

自底向上的伸展方式很容易理解，但是在实现的过程中需要使用栈来保存访问路径进行回溯，但是自顶向下的实现方式能够只用O(1)的存储方式，实现同样的实现效果。自自顶向下的伸展树实现首先将树划分成三个树，左树右树和中树，开始时左树和右树都是空树，待伸展的树为中树。
单旋转的的实现很简单，如图4所示，只需要将待查找节点Y的的父节点X作为右树（R）最左节点的左儿子即可。



图4：自顶向下的伸展树单旋转

一字型则只需要待查找节点Z的父节点Y和其祖父节点X进行一次旋转即可，然后做但选择将Y节点作为R树的最左节点的左儿子。如图5所示


图5：自顶向下的伸展树一字型旋转

之字形则不要像一字型一样，只要进行两次不同方向的单旋转即可，如图6所示，Z为查找节点，我们只需将Z的父节点及其右子树作为L树最右节点的右孩子即可，而其祖父节点X及其右子树作为R树最左节点的左孩子即可。


图6：自顶向下的伸展树之字形旋转

在最终查询节点在中树达到了树根的位置，我们既可以做最终的合并，合并的规则如图7所示，将最终查询节点的左子树作为L树最左节点的右树，并把左树作为根节点的左树，而把根节点的右树作为R树最右节点的左树 ，并把R树作为根节点的右树。


图7：最终合并

伸展的实现

从上面的分析来看，我们在实现的时候仅需要在一字型的时候进行像平衡二叉树的单旋操作，而单旋转和之字形只需要简单的链改变。我们的实现思路如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
描述：在查询一个节点后进行伸展旋转，将其推到根节点位置
输入：查找的节点的值x，伸展树树根root
输出：新的树根
初始化leftHeader=headerNode，rightHeader=headerNode
初始化leftMax=leftHeader,rightMin=rightHeader
循环
	if x<root节点的值，说明在左子树
		if root.left为null，说明左子树为空，查找失败
			调整结束，跳出循环
		if x小于root.left的值，一字型情况
			root=rotateWithLeftChild(root)，将root的左孩子调整到root的位置
		//不论是x小于还是大于root.left的值，下一步都是将root作为R的最左孩子的左儿子
		rightMin.left=root
		rightMin=root//调整最左孩子
		root=root.left
	if x>root节点的值，说明在右子树
		如果root.right等于null,说明右子树为空，查找失败
			调整结束，跳出循环
		如果x大于root.right的值，右一字型情况
			root=rotateWithRightChilde(root)
		leftMax.right=root
		leftMax=root
		root=root.right
	else 等于的情况
		中树根已经为x，直接跳出循环
开始合并
leftMax.right=root.left
rightMin.left=root.right
root.left=leftHeader.right
root.right=rightHeader.left
return root

在这里有个小细节，就是我们在rightMin=root，root=root.left的时候，rightMin保持的root的left依然存在 ，我这里之所以没有把它置null是因为在最后合并的时候会同一经rightMin.left置成root.right，而且没一轮如果符合条件，都会发生置换。我们的Java实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
	public BinaryNode<T> splay(T x, BinaryNode<T> root){
		BinaryNode< T> headerNode=new BinaryNode<>(null);//头节点，随便定义其值
		BinaryNode<T>rightHeader=headerNode;
		BinaryNode<T>leftHeader=headerNode;
		BinaryNode<T>leftMax=leftHeader;
		BinaryNode<T>rightMin=rightHeader;
		if(root==null)
			return root;
		
		while(true) {
			if(x.compareTo(root.element)<0) {
				if(root.left==null)
					break;
				if(x.compareTo(root.left.element)<0)
					root=rotateWithLeftChild(root);
				rightMin.left=root;
				rightMin=root;
				root=root.left;
			}else if(x.compareTo(root.element)>0) {
				if(root.right==null)
					break;
				if(x.compareTo(root.right.element)>0)
					root=rotateWithRightChild(root);
				leftMax.right=root;
				leftMax=root;
				root=root.right;
			}else //等于的情况，结束循环
				break;
		}
		//开始合并
		leftMax.right=root.left;
		rightMin.left=root.right;
		root.left=leftHeader.right;
		root.right=rightHeader.left;
		return root;
	}
}

伸展树的插入实现

插入的实现基本思路是，如果根节点为空，直接返回新生成的节点，如果不为空，则对查找元素x在树上进行伸展操作，如果新的树根为x，那么原来树中有x，不再进行插入；如果新根的节点的值小于x，那么直接将新根节点作为x的左儿子，新根的右儿子作为x的右儿子，返回x节点；如果新根的节点的值大于x，思路类似。其伪代码标书如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
描述：插入一个节点到伸展树中
输入：待插入节点的值x，伸展树的树根root
输出：插入后的新根newRoot
if root==null
	返回newNode(x)
root=spaly(x,root)//伸展
if x>root的值
	newRoot=newNode(x)
	newRoot.left=root
	newRoot.right=root.right
	root.right=null//因为root的right变到newRoot的right去了
else if x<root的值,应该插在左树上
	newRoot=newNode(x)
	newRoot.right=root
	newRoot.left=root.left
	root.left=null
else //等于的情况
	newRoot=root
返回newRoot

其Java实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public BinaryNode<T> insert(T x, BinaryNode<T> root){
	if(root==null)
		return new BinaryNode<T>(x);
	root=splay(x, root);
	BinaryNode<T>newRoot;
	if(x.compareTo(root.element)>0) {
		newRoot=new BinaryNode<T>(x);
		newRoot.left=root;
		newRoot.right=root.right;
		root.right=null;
	}else if(x.compareTo(root.element)<0){
		newRoot=new BinaryNode<T>(x);
		newRoot.right=root;
		newRoot.left=root.left;
		root.left=null;
	}else {
		newRoot=root;
	}
	return newRoot;
}

我们来测试一下，插入从1到7的插入并且再次插入1，层序遍历后结果是如下



图8：测试添加

伸展树的删除实现

删除的过程很简单思路也很简单，如果树中不包含x,那么直接返回，如果找到了，进行伸展操作。接着如果左子树为空，则右儿子直接作为根返回，如果左子树不为空，则找到左儿子的最右节点，将根节点的右子树左为左儿子最右节点的右子树，从而完成删除，整个代码实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void remove(T x) {
	BinaryNode<T> newRoot=splay(x,root);
	if(x.compareTo(newRoot.element)!=0) {
		root= newRoot;
	}else {//不等于的情况
		if(newRoot.left==null) {//左子树等于null
			newRoot=newRoot.right;
		}else {
			BinaryNode<T> leftMax=newRoot.left;
			while(leftMax.right!=null) {
				leftMax=leftMax.right;
			}
			leftMax.right=newRoot.right;
			newRoot=newRoot.left;
		}
		root=newRoot;
	}
}

伸展树的应用场景

除了常用的伸展，插入，删除操作外，伸展树常用的功能还有合并两个树（join），以x分界分裂一个树(split)，其算法思想和前面类似。
一个有趣应用是用伸展树找到区间中的所有节点，具体的应用及其解决办法可以参见这几个好的博文
伸展树的应用1
伸展树的应用2
伸展树的应用3

坚持原创技术分享，您的支持将鼓励我继续创作！